#include <iostream>
#include <vector>
#include <deque>
using namespace std;
class Solution
{
public:
    vector<int> asteroidCollision(vector<int> &asteroids)
    {
        vector<int> st;
        for (auto aster : asteroids)
        {
            bool alive = true;
            while (alive && aster < 0 && !st.empty() && st.back() > 0)
            {
                alive = st.back() < -aster; // aster 是否存在
                if (st.back() <= -aster)
                { // 栈顶行星爆炸
                    st.pop_back();
                }
            }
            if (alive)
            {
                st.push_back(aster);
            }
        }
        return st;
    }

    vector<int> asteroidCollision_2(vector<int> &asteroids)
    {
        deque<int> ret;
        for (int num : asteroids)
        {
            if (num < 0)
            {
                while (!ret.empty() && num < 0 && ret.back() > 0)
                {
                    if (-num == ret.back())
                    {
                        ret.pop_back();
                        num = 0;
                        break;
                    }
                    else if (-num > ret.back())
                        ret.pop_back();
                    else
                        num = ret.back();
                }
                if (num < 0)
                    ret.push_back(num);
            }
            else
                ret.push_back(num);
        }
        return vector<int>(ret.begin(), ret.end());
    }
};
int main()
{
    Solution s;
    vector<int> asteroids = {-2, 4, 3, -4, 7, -3, 6, 10};
    vector<int> ans = s.asteroidCollision_2(asteroids);
    for (int a : ans)
    {
        cout << a << " ";
    }
    cout << endl;
    system("pause");
    return 0;
}
